// Written by Craig'n'Dave
using System;
// Hash table using an array
namespace ConsoleApp1
{
    class Program
    {
        static int hashing_function(string item, int table_size)
        {
            // Simple hashing algorithm adds ascii values of characters modulus table size
            int total = 0;
            for (int character = 0; character < item.Length; character++)
            {
                total = total + item[character];
            }
            return total % table_size;
        }

        static string[] create_hash_table(string[] items, int table_size)
        {
            // Reserve memory for hashing table
            string[] hash_table = new string[table_size];
            int h;
            // Place data in hashing table
            for (int index = 0; index < items.Length; index++)
            {
                h = hashing_function(items[index], table_size);
                if (hash_table[h] != null)
                {
                    Console.WriteLine("Collision inserting " + items[index] + " at " + h);
                    // On collision insert in next available space
                    while (hash_table[h] != null)
                    {
                        h = h + 1;
                    }
                }
                hash_table[h] = items[index];
                Console.WriteLine("Inserted " + items[index] + " at position " + h);
            }
            return hash_table;
        }

        static void search_hash_table(string item_to_find, string[] hash_table)
        {
            bool found = false;
            int h;
            h = hashing_function(item_to_find, (hash_table.Length));
            // Attempt to find item at hash value
            if (hash_table[h] != null)
            {
                if (hash_table[h] == item_to_find)
                {
                    found = true;
                }
                else
                {
                    // Degrade to linear search for collisions
                    while ((h < hash_table.Length) && (!found))
                    {
                        if (hash_table[h] != item_to_find)
                        {
                            h = h + 1;
                        }
                        else
                        {
                            found = true;
                        }
                    }
                }
            }
            if (found)
            {
                Console.WriteLine("Item found at position " + h);
            }
            else
            {
                Console.WriteLine("Item not found");
            }
        }

        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            // The larger the table the fewer collisions
            int table_size = 10;
            string[] hash_table = new string[table_size];
            string item_to_find;
            hash_table = create_hash_table(items, table_size);
            Console.Write("Enter the state to find: ");
            item_to_find = Console.ReadLine();
            search_hash_table(item_to_find, hash_table);
        }
    }
}
